package com.demo.java.OD551_600.OD555;

import java.util.Scanner;
import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【二维伞的雨滴效应(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146534179
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 读取前序遍历的输入并转换成整数数组
        int[] pre_order = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        TreeNode root = new TreeNode(pre_order[0]);  // 根节点是前序遍历的第一个元素

        // 使用栈来辅助构建二叉搜索树
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        TreeNode helper = new TreeNode(-1);  // 用来辅助判断是否符合二叉搜索树性质
        boolean flag = true;  // 用来标记是否为合法的二叉搜索树

        // 根据前序遍历的顺序构建二叉搜索树
        for (int i = 1; i < pre_order.length; i++) {
            TreeNode node = stack.peekLast();  // 获取栈顶元素
            TreeNode currentNode = new TreeNode(pre_order[i]);  // 创建当前节点

            // 处理当前节点
            while (!stack.isEmpty() && stack.peekLast().val < currentNode.val) {
                node = stack.removeLast();  // 移除栈顶节点
                if (!stack.isEmpty()) {
                    helper = stack.peekLast();  // 更新辅助节点
                }
            }

            // 如果当前节点的值大于父节点，说明它是右子节点
            if (node.val < currentNode.val) {
                node.right = currentNode;
                helper = node;  // 更新辅助节点
            } else {  // 否则是左子节点
                if (currentNode.val < helper.val) {
                    flag = false;  // 不符合二叉搜索树属性
                    break;
                }
                node.left = currentNode;
            }

            stack.addLast(currentNode);  // 将当前节点压入栈
        }

        // 判断二叉搜索树是否合法并输出结果
        if (flag) {
            TreeNode leftNode = root;
            // 查找根节点的左子节点
            while (leftNode.left != null || leftNode.right != null) {
                if (leftNode.left != null) {
                    leftNode = leftNode.left;
                } else {
                    leftNode = leftNode.right;
                }
            }

            TreeNode rightNode = root;
            // 查找根节点的右子节点
            while (rightNode.left != null || rightNode.right != null) {
                if (rightNode.right != null) {
                    rightNode = rightNode.right;
                } else {
                    rightNode = rightNode.left;
                }
            }

            // 输出根节点的左子节点和右子节点
            System.out.println("1 " +
                    (leftNode.val == root.val ? 0 : leftNode.val) + " " +
                    (rightNode.val == root.val ? 0 : rightNode.val));
        } else {
            System.out.println("0 0 0");  // 输出非法情况
        }
        return;
    }

    // 定义二叉树的节点
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }
    }
}